package Chapter2;

import java.sql.SQLOutput;

public class SortedSinglyList<T extends Comparable<? super T>> extends SinglyList<T> {
    protected boolean asc;

    public SortedSinglyList(boolean asc) {
        super();
        this.asc = asc;
    }

    public SortedSinglyList() {
        this(true);
    }

    public SortedSinglyList(T[] values, boolean asc) {
        this(asc);
        for (int i = 0; i < values.length; i++)
            this.insert(values[i]);
    }

    public SortedSinglyList(T[] values) {
        this(values, true);
    }

    public void set(int i, T x) {
        throw new java.lang.UnsupportedOperationException("set(int i,T x)");
    }

    public Node<T> insert(int i, T x) {
        throw new java.lang.UnsupportedOperationException("insert(int i,T x)");
    }

    public Node<T> insert(T x) {
        if (x == null)
            return null;
        Node<T> front = this.head, p = front.next;
        while (p != null && (this.asc ? x.compareTo(p.data) >= 0 : x.compareTo(p.data) <= 0)) {
            front = p;
            p = p.next;
        }
        front.next = new Node<T>(x, p);
        return front.next;
    }

    public String toString() {
        return super.toString() + "," + (this.asc ? "升序" : "降序");
    }

    public Node<T> search(T key) {
        Node<T> p = this.head.next;
        while (p != null && (this.asc ? key.compareTo(p.data) > 0 : key.compareTo(p.data) < 0))
            p = p.next;
        if (p != null && key.compareTo(p.data) == 0)
            return p;
        return null;
    }

    public T remove(T key) {
        Node<T> front = this.head, p = front.next;
        while (p != null && (this.asc ? key.compareTo(p.data) > 0 : key.compareTo(p.data) < 0)) {
            front = p;
            p = p.next;
        }
        if (p != null && key.compareTo(p.data) == 0) {
            front.next = p.next;
            return p.data;
        }
        return null;
    }

    public SortedSinglyList(SortedSinglyList<T> list) {
        super(list);
        this.asc = list.asc;
    }

    public void deleteDuplicates() {
        Node<T> front = head.next, p = front.next;
        while (front != null && p != null) {
            if (front.data.equals(p.data))
                front.next = p.next;
            else
                front = front.next;
            p = front.next;
        }
    }

    public SortedSinglyList(SinglyList<T> list, boolean asc) {
        this(asc);
        for (Node<T> p = list.head.next; p != null; p = p.next)
            this.insert(p.data);
    }

    public SortedSinglyList(SinglyList<T> list) {
        this(list, true);
    }

    public boolean equals(Object obj) {
        System.out.println(this.getClass().getName() + ".equals(" + obj.getClass().getName() + "),");
        if (obj == this)
            return true;
        if (obj instanceof SortedSinglyList<?>) {
            SortedSinglyList<T> list = (SortedSinglyList<T>) obj;
            return this.asc = list.asc && super.equals(list);
        }
        return false;
    }

    public void concat(SinglyList<T> list) {
        throw new UnsupportedOperationException("concat(SinglyList<T> list)");
    }

    public void addAll(SinglyList<T> list) {
        for (Node<T> p = list.head.next; p != null; p = p.next)
            this.insert(p.data);
    }

    public SortedSinglyList<T> union(SinglyList<T> list) {
        SortedSinglyList<T> result = new SortedSinglyList<T>(this);
        result.addAll(list);
        return result;
    }

    public void merge(SortedSinglyList<T> list) {
        if (this.asc != list.asc) {
            for (Node<T> p = list.head.next; p != null; p = p.next)
                this.insert(p.data);
            return;
        }
        Node<T> front = this.head, p = front.next;
        Node<T> q = list.head.next;
        while (p != null && q != null) {
            if ((p.data).compareTo(q.data) < 0) {
                front = p;
                p = p.next;
            } else {
                front.next = q;
                q = q.next;
                front = front.next;
                front.next = p;
            }
        }
        if (q != null)
            front.next = q;
        list.head.next = null;
    }
}
